{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #推理二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #array #hash-table #divide-and-conquer #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #数组 #哈希表 #分治 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: deduceTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #推理二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>某二叉树的先序遍历结果记录于整数数组 <code>preorder</code>，它的中序遍历结果记录于整数数组 <code>inorder</code>。请根据 <code>preorder</code> 和 <code>inorder</code> 的提示构造出这棵二叉树并返回其根节点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>注意：<code>preorder</code> 和 <code>inorder</code> 中均不含重复数字。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/19/tree.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]\n",
    "\n",
    "<strong>输出: </strong>[3,9,20,null,null,15,7]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>preorder = [-1], inorder = [-1]\n",
    "\n",
    "<strong>输出:</strong> [-1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= preorder.length &lt;= 3000</code></li>\n",
    "\t<li><code>inorder.length == preorder.length</code></li>\n",
    "\t<li><code>-3000 &lt;= preorder[i], inorder[i] &lt;= 3000</code></li>\n",
    "\t<li><code>inorder</code> 均出现在 <code>preorder</code></li>\n",
    "\t<li><code>preorder</code> 保证 为二叉树的前序遍历序列</li>\n",
    "\t<li><code>inorder</code> 保证 为二叉树的中序遍历序列</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>注意：本题与主站 105 题重复：<a href=\"https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/\" rel=\"noopener noreferrer\" target=\"_blank\">https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/</a></p>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [zhong-jian-er-cha-shu-lcof](https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [zhong-jian-er-cha-shu-lcof](https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,9,20,15,7]\\n[9,3,15,20,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deduceTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "        # def myBuildTree(inorder_left: int, inorder_right: int):\n",
    "        #     if inorder_left > inorder_right:\n",
    "        #         return None\n",
    "        #     val = preorder.pop(0)\n",
    "        #     root = TreeNode(val)\n",
    "        #     idx = index[val]\n",
    "        #     root.left = myBuildTree(inorder_left, idx-1)\n",
    "        #     root.right = myBuildTree(idx+1, inorder_right)\n",
    "        #     return root\n",
    "        # n = len(preorder)\n",
    "        # # 构造哈希映射，帮助我们快速定位根节点\n",
    "        # index = {element: i for i, element in enumerate(inorder)}\n",
    "        # return myBuildTree(0, n - 1)\n",
    "\n",
    "\n",
    "\n",
    "        if not preorder:\n",
    "            return None\n",
    "        root = TreeNode(preorder[0])\n",
    "        stack = [root]\n",
    "        inorderIndex = 0\n",
    "        n = len(preorder)\n",
    "        for i in range(1, n):\n",
    "            node = stack[-1]\n",
    "            if node.val != inorder[inorderIndex]:\n",
    "                node.left = TreeNode(preorder[i])\n",
    "                stack.append(node.left)\n",
    "            else:\n",
    "                while stack and inorderIndex < n and stack[-1].val == inorder[inorderIndex]:\n",
    "                    node = stack.pop()\n",
    "                    inorderIndex += 1\n",
    "                node.right = TreeNode(preorder[i])\n",
    "                stack.append(node.right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deduceTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:\n",
    "        def recur(root, left, right):\n",
    "            if left > right: return                               # 递归终止\n",
    "            node = TreeNode(preorder[root])                       # 建立根节点\n",
    "            i = hmap[preorder[root]]                              # 划分根节点、左子树、右子树\n",
    "            node.left = recur(root + 1, left, i - 1)              # 开启左子树递归\n",
    "            node.right = recur(i - left + root + 1, i + 1, right) # 开启右子树递归\n",
    "            return node                                           # 回溯返回根节点\n",
    "\n",
    "        hmap, preorder = {}, preorder\n",
    "        for i in range(len(inorder)):\n",
    "            hmap[inorder[i]] = i\n",
    "        return recur(0, 0, len(inorder) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deduceTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "        def build(preorder_left, preorder_right, inorder_left, inorder_right):\n",
    "            if preorder_left > preorder_right:\n",
    "                return None\n",
    "            prerootindex = preorder_left\n",
    "            inrootindex = hashdict[preorder[prerootindex]]\n",
    "            lefttreenums = inrootindex - inorder_left\n",
    "            root = TreeNode(preorder[prerootindex])\n",
    "            root.left = build(preorder_left+1, preorder_left+lefttreenums, inorder_left, inrootindex-1)\n",
    "            root.right = build(preorder_left+lefttreenums+1, preorder_right, inrootindex+1, inorder_right)\n",
    "            return root\n",
    "        \n",
    "        n = len(preorder)\n",
    "        hashdict = {key:value for value, key in enumerate(inorder)}\n",
    "        return build(0, n-1, 0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deduceTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "        if inorder:\n",
    "            ind = inorder.index(preorder.pop(0))\n",
    "            root = TreeNode(inorder[ind])\n",
    "            root.left = self.deduceTree(preorder, inorder[0:ind])\n",
    "            root.right = self.deduceTree(preorder, inorder[ind+1:])\n",
    "            return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deduceTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "        def build(inorder: List[int]):\n",
    "            if len(inorder) == 0:\n",
    "                return None\n",
    "            if len(inorder) == 1:\n",
    "                head = preorder.pop(0)\n",
    "                return TreeNode(head)\n",
    "            head = preorder.pop(0)\n",
    "            i = inorder.index(head)\n",
    "            node = TreeNode(head)\n",
    "            # print(inorder[0:i], inorder[i])\n",
    "            node.left = build(inorder[0:i])\n",
    "            # print(inorder[i], inorder[i + 1:])\n",
    "            node.right = build(inorder[i + 1:])\n",
    "            return node\n",
    "\n",
    "        if len(inorder) == 1:\n",
    "            return TreeNode(inorder[0])\n",
    "        ans = build(inorder)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deduceTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "        if len(preorder) == 1:\n",
    "            return TreeNode(preorder[0])\n",
    "        if preorder == []:\n",
    "            return None\n",
    "        find_id = inorder.index(preorder[0])\n",
    "        return TreeNode(\n",
    "            preorder[0],\n",
    "            self.deduceTree(preorder[1:1+find_id], inorder[:find_id]),\n",
    "            self.deduceTree(preorder[find_id+1:], inorder[find_id+1:]))\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deduceTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return\n",
    "        # 在前序遍历序列中获取根结点\n",
    "        root_val=preorder[0]\n",
    "        root=TreeNode(root_val)\n",
    "        # 在中序遍历序列中找到根结点（切割点）索引\n",
    "        index=inorder.index(root_val)\n",
    "        # 切割中序遍历序列\n",
    "        inorder_left=inorder[:index]\n",
    "        inorder_right=inorder[index+1:]\n",
    "        # 切割前序遍历序列\n",
    "        preorder_left=preorder[1:1+len(inorder_left)]\n",
    "        preorder_right=preorder[1+len(inorder_left):]\n",
    "        # 继续递归\n",
    "        root.left=self.deduceTree(preorder_left,inorder_left)\n",
    "        root.right=self.deduceTree(preorder_right,inorder_right)\n",
    "        return root"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
